/**
 * 712. 两个字符串的最小ASCII删除和
 * https://leetcode-cn.com/problems/minimum-ascii-delete-sum-for-two-strings/
 */
public class Solutions_712 {
    public static void main(String[] args) {
        String s1 = "sea", s2 = "eat";  // output: 231
//        String s1 = "delete", s2 = "leet";  // output: 403

        int result = minimumDeleteSum(s1, s2);
        System.out.println(result);
    }

    /**
     * dp[4][6] = 231：s2 中前 4 个字符与 s1 中前 6 个字符，最小删除和是 403
     *
     *         s    e    a
     *    0    s    se   sea
     * e  e    se   s    sa
     * a  ea   sea  sa   s
     * t  eat  seat sat  st
     */
    public static int minimumDeleteSum(String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        char[] arr1 = s1.toCharArray(), arr2 = s2.toCharArray();
        // s1 为列，s2 为行
        int[][] dp = new int[len2 + 1][len1 + 1];
        dp[0][0] = 0;

        // dp 初始值计算
        for (int i = 1; i <= len1; i++) {
            dp[0][i] = dp[0][i - 1] + arr1[i - 1];
        }
        for (int j = 1; j <= len2; j++) {
            dp[j][0] = dp[j - 1][0] + arr2[j - 1];
        }
        for (int i = 1; i <= len2; i++) {
            for (int j = 1; j <= len1; j++) {
                if (arr1[j - 1] == arr2[i - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int m = dp[i][j - 1] + arr1[j - 1];
                    int n = dp[i - 1][j] + arr2[i - 1];
                    dp[i][j] = Math.min(m, n);
                }
            }
        }
        return dp[len2][len1];
    }
}
